package com.xufx.algorithm.doublepointer;

import java.util.Arrays;
import java.util.Collections;

/**
 * leetcode 16. 3Sum Cloest
 * @link https://leetcode.cn/problems/3sum-closest/description/
 * describe: Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
 *
 * Return the sum of the three integers.
 *
 * You may assume that each input would have exactly one solution.
 *
 * example:
 * Input: nums = [-1,2,1,-4], target = 1
 * Output: 2
 * Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
 *
 * Notice:
 *  1. 类似于三数之和，利用循环 + 双指针减少计算的时间复杂度
 */
public class Leetcode163SumClosest {
    public static void main(String[] args) {
        int[] nums = {-1, 2, 1, -4};
        int target = 1;
        int result = threeSumClosest(nums, target);
        System.out.println( "bingo == " + result);
    }

    private static int threeSumClosest(int[] nums, int target){
        //  处理特殊情况
        if(nums.length == 3){
            return nums[0] + nums[1] + nums[2];
        }
        Arrays.sort(nums);
        int len = nums.length;
        int result = Integer.MAX_VALUE;
        for(int i = 0; i < len; i ++){
            // 定义左右指针
            int left = i + 1;
            int right = len - 1;
            while(left < len && right > i && left < right){
                int cursum = nums[i] + nums[left] + nums[right];
                if(target - cursum > 0){
                    result = Math.abs(cursum - target) > Math.abs(result - target) ? result : cursum;
                    left ++;
                }else if(target - cursum < 0){
                    result = Math.abs(cursum - target) > Math.abs(result - target) ? result : cursum;
                    right --;
                }else{
                    return cursum;
                }
            }
        }
        return result;
    }
}
